# 221 最大正方形
# https://leetcode.cn/problems/maximal-square/description/
# Date: 2024/11/4
# 与dp14_lc1277类似

def maximalSquare(matrix: list[list[str]]) -> int:
    m, n = len(matrix), len(matrix[0])  # 行数, 列数
    dp = [[0] * n for _ in range(m)]
    maxm = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == "0":
                dp[i][j] = 0
            else:
                dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
            maxm = max(maxm, dp[i][j])

    return maxm ** 2


print(maximalSquare([["0", "1"], ["1", "0"]]))
print(maximalSquare(
    [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]))
